1. Field of the Invention
The present invention relates to the processing of digital images and more specifically to the conversion between images transported in raster order to images transported in block order.
2. Related Art
In modern electronics, a digital image comprises a set of pixels. Each pixel has associated with it a pixel value and pixels are usually laid out in a two-dimensional grid covering the image. The pixel value can be a single numeric value or a set of numeric values. For example, in a monochromatic image, a pixel value is typically a single number representing the intensity or luminance. For polychromatic or color images, the pixel value can be one of several schemes based on the type of color space used. It can be represented by a number for luminance (Y) and two numbers for chrominance (Cr, Cb). It can also be red-green-blue (RGB) or cyan-yellow-magenta-black (CYMK) color spaces. The space of one of these colors is often referred to as color planes, e.g., RGB color spaces are often referred to as comprising a red color plane, a green color plane and a blue color plane.
Conventionally, image sources generate image data with pixels either in raster order. FIG. 1 shows the raster ordering of pixels. By convention it begins with the upper left pixel of an image followed by pixels scanning from left to right, followed by a scanning from left to right on the subsequent line until the rightmost pixel on the bottom line of the image is reached. Less conventionally, the scanning can proceed first from right to left then top to bottom or top to bottom and then left to right, etc. For the sake of simplicity, the left to right top scanning is considered, although one of ordinary skill in the art will recognize the equivalence of the different orientations.
In video applications, the raster stream of pixels from one image is immediately followed by a stream of pixels representing a subsequent image in a sequence of images. More specifics as to particulars as to the pixel representation and stream format can be found in various standards, such as motion pictures experts group (MPEG) or motion joint photographic experts group (MJPEG).
Like image sources, typical display devices operate with raster ordering of pixels. However, because of the large amount of data present in raw image data, high degrees of image compression is often sought for the storage or transport of digital images as well as video applications. Because images are naturally two-dimensional in nature, the best image compression techniques operation on two dimensional blocks For example the joint photographic experts group (JPEG) compression algorithm first divides an image into a square block of 8×8 pixels then compresses each block.
Ideally, for the input to an image compressor/encoder the image data should be presented in block order and the output to an image decompressor/decoder should be received in block order. FIG. 2 shows the simplest block ordering. Here in this example the blocks are 4×4 and additional spacing between some pixels are shown for clarity. Within each block the format is not important but raster ordering within a block is often seen as most convenient.
A difficulty arises because image sources and image displays tend to operate in raster order and image compression systems operate in block order. Because of this, an image compressor/encoder must store multiple raster lines of pixels until all the pixels of a block are received. Similarly, an image decompressor/decoder which would present image data in block order, enough data blocks must be stored until store blocks until a complete raster line is received. Because the storage need only be large as one row of blocks, referred to as an image band, memory requirements can be as little as a n×w pixels where n is the height of a block and w is the width of an image.
FIGS. 3A-E shows an exemplary buffer for storing an image band for raster to block conversion in its various states of operation. The buffer comprises n×w pixels and is shown in array form for clarity, but in principle is most likely a contiguous linear memory. In this example a block size of 4×4 is used with an image width of 20 pixels. FIG. 3A shows the buffer after one raster line has been received. FIG. 3B shows the buffer after a second raster line has been received. FIG. 3C shows the buffer after the entire image band is written. FIG. 3D shows the buffer after the first block is read and the memory corresponding to the block is vacated. FIG. 3E shows the buffer after a second block is read and the corresponding memory is vacated.
Clearly an image band buffer can be used to convert from raster order to block order. However, the difficulty arises when as the first image band is read from the buffer, a second image band is written in. FIG. 4A shows the image band buffer with the first block vacated. As the first raster line of the second image band is received, the first four pixels can be stored in the vacated memory. However, as shown in FIG. 4B the memory for the next four pixels is still occupied by the second block. These memory locations are shown in solid black.
One of the simplest and effective solutions is to use two image buffers. FIGS. 5A-F shows the operation of a dual image band buffer system using the same exemplary dimensions as in FIGS. 4A-D and FIGS. 5A-B. In FIG. 5A, the first raster line from the first image band is stored into image buffer 502. In FIG. 5B, the entire first image band is stored into image buffer 502. In FIG. 5C, the first block is read from image buffer 502 at the same time the first 16 pixels from the first raster line from a second image band are received and stored into image buffer 504. In FIG. 5D, the second block is read from image buffer 502 and at the same time the next 16 pixels from the first and second raster lines from the second image band are received and stored into image buffer 504. In FIG. 5E, all the blocks from the first image band have been read from image buffer 502 and the entire image band is stored in image buffer 504. At this point image buffer 502 is ready to receive a third image band and image buffer 504 has blocks ready to be read. In FIG. 5F the first image block of the second image band is read from image buffer 504 and the first 16 pixels from the first raster line from a third image band is received stored in image buffer 502. This process continues back and forth between the two image buffers in a technique known as ping-ponging.
FIG. 6 shows a typical implementation of a ping-ponging raster to block converter. Converter 600 described here is similar to that described in the background section of U.S. Pat. No. 5,446,560. The converter comprises image band buffer 602 and image band buffer 604, multiplexer 606, address generators 608 and 610 and inverter 612.
A stream of pixels in raster order is supplied to both image band buffer 602 and image band buffer 604. A state input is supplied to the write enabled input of image band buffer 602 and to inverter 612. The output of the inverter is supplied to the write enable input of image band buffer 604. This ensures that the input data received is written by only one of the image band buffers. The outputs of the image band buffers are fed to multiplexer 606 which selects the signal based on the same state input.
The address of image band buffer 602 is provided by address generator 608 and the address of image band buffer 604 is provided by address generator 610. Address generator 608 generates an address which dictates the location in image band buffer 602 which is read from and written to; address generator 610 generates the address of locations in image band buffer 604 which is read from and written to.
When the state input is set to 0 image band buffer 604 is written to and the multiplexer selects image band buffer 602 to be read from, causing image band buffer 604 to fill and image band buffer 602 to empty. Once image band buffer 604 is full, the state input changes to state 1. When the state is set to 1 the roles are reversed. Image band buffer 602 is written to and the multiplexer selects image band buffer 604 to be read from, causing image band buffer 604 to fill and image band buffer 602 to empty.
To convert from raster to block ordering, address generator 610 might generate an address sequence in raster order in state 0, and then in state 1, generate an address sequence which would read the pixels out of image band buffer 604 in block order. Address generator 608 operates similarly, but generates the raster order addresses in state 1, and the block ordered address sequence in state 0. Image band buffer, and a continuous stream of pixels can be output from the image band buffers into which data is not being written.
While this architecture converts from raster order to pixel order effectively, it does at the expense of twice the memory cost. For images, even an image band can occupy significant memory, for example, for three color pixels at one byte each and an image width of 1024 pixels and an 8×8 block size, 24 kilobytes of RAM are needed for buffering. While in today's age of copious memory, this may not seem like a lot, video memory is usually very high performance and expensive, especially when incorporated into an integrated circuit. Therefore reduction of memory requirements for raster to block order is needed.
The aforementioned U.S. Pat. No. 5,446,560, does provide a system for conversion between raster and block ordering that requires only one image band buffer, but it is complicated and not easily scalable. This design trades off savings from reduced memory for the complexity of the additional circuitry required to implement this solution. Therefore there is a need in the industry for a conversion system between block and raster ordering that does not require large amounts of memory and that is simple to implement and scalable.